package com.sjf.day02.Recursion;

import java.util.Arrays;
import java.util.List;

/**
 * 八皇后问题
 *
 * @author <huangtang>
 * @since 2021/12/24 10:04
 **/
public class Queue8 {

    int max = 8;//共有多少个皇后
    int[] array = new int[max]; //皇后放置位置的结果,下标表示行，值表示列
    static int count = 0; //用于统计有多少中方法
    static int num = 0;
    public static void main(String[] args) {
        //测试八皇后是否正确
        Queue8 queue8 = new Queue8();
        queue8.check(0); //放第一个皇后，数组下标 从0开始
        System.out.printf("总共 %d 种方法 \n",count);
        System.out.println(num);
        short s1 =1;
        System.out.println(2*8);
    }

    //编写一个方法，放置第n个皇后
    public void check(int n){
        if(n == max){ //放到第9个皇后,此时直接返回
            count++; //解法+1
            print(); //打印路径
            return;
        }
        //依次放入皇后，并判断是否冲突
        for (int i = 0; i < max; i++) {
            //先把当前这个皇后，放在第n行的第一列
            array[n] = i;
            //判断当防止第n个皇后到i列时是否冲突
            if(isConflict(n)){
                //不冲突，继续放置后面的皇后
                check(n+1);
            }
            //如果冲突，就返回上一个栈的for循环,重新将皇后放在该行的下一列中
            //继续判断是否冲突，无冲突，则放置，有冲突，则回溯继续向后遍历
        }
    }

    /**
     * 放置皇后时，检测是否与已经摆放的皇后发生冲突
     * @param n 表示第n个皇后
     * @return  true 不冲突
     *          false 冲突
     *
     */
    public boolean isConflict(int n){
        num++;
        for (int i = 0; i < n; i++) {
            //array[i] == array[n] 判断两个皇后是否再同一列
            //Math.abs(n-i) == Math.abs(array[n] - array[i]) 判断两个皇后是否在同一斜线上
            //没有必要判断是否在同一行，数组向后遍历，行数自动递增
            if(array[i] == array[n] || Math.abs(n-i) == Math.abs(array[n] - array[i])){
                return false;
            }
        }
        return true;
    }


    /**
     *   将皇后拜访的位置输出
     */
    public void print(){
        for (int i = 0; i < array.length; i++) {
            System.out.print(array[i]+ " ");
        }
        System.out.println();
    }


}
